// 214. 最短回文串，太难了，不做了
/**
 * @param {String} s
 * @return {String}
 */
var shortestPalindrome_five = function(s) {
    /**
     * five方法
     * 获取s的倒叙，然后依次添加进去，判断是否是回文
     * 超时
     */


     


    /**
     * 
     * @param {String} s 
     */
     function isPalindrome(s){
         //中心扩展法
        //  const  len = s.length
        //  let l = 0
        //  let r = 0
        //  if(len&1){//基数长度
        //     l = r = Math.floor(len/2)
        //  } else{
        //     r = len/2
        //     l=r-1
        //  }

        //  while(l!=-1&&r!=s.length){
        //     if(s.charAt(l)!==s.charAt(r)) return false
        //     l--
        //     r++
        //  }
        //  return true

        //一个字符串是回文，当且仅当他和自身的逆序相同
        const r = Array.from(s).reverse().join('')
        return s===r
     }
     if(isPalindrome(s)) return s
     const sr = Array.from(s).reverse()
     let p = ''
     for (const it of sr) {
        p+=it
        const ans = p+s
        if(isPalindrome(ans)) return ans
     }

};


/**
 * @param {string} s
 * @return {string}
 */
var shortestPalindrome = function(s) {
    /**
     *  找原始字符中最长的回文串，获取剩下部分，reverse加到前面
     * ，使用hash进行字符串相等判断
     */

     const mod = 1000008
     const base = 55
     let left = 0
     let right = 0
     let lBase = 1
     let lastIndex = -1 //回文串的最后一位
     for(let i=0;i<s.length;i++){
         const c = s.charCodeAt(i)
         //把c作为右边位
        right= (right*base%mod +c)%mod
        //把c作为左边位
        left = (c*lBase%mod + left)%mod
        
        lBase = lBase*base%mod

        if(left===right) lastIndex = i

     }
     const last = lastIndex===s.length-1?'':s.substring(lastIndex+1)
     const pre = Array.from(last).reverse().join('')
     return pre+s

};

const p = 'abcd'
const s = shortestPalindrome(p)
console.log(s)